//二叉树的各种遍历
const tree = {
  val:1,
  left:{
    val:2,
    left:{
      val:4,
      left: null,
      right: null
    },
    right: {
      val:5,
      left: null,
      right: null
    }
  },
  right:{
    val:3,
    left:{
      val:6,
      left: null,
      right: null
    },
    right:{
      val:7,
      left: null,
      right: null
    }
  }
};

/** 深度优先遍历---递归实现 */
//前序遍历
function pre(node){
 if(!node) return;
 console.log(node.val);
 pre(node.left);
 pre(node.right);
}
// pre(tree); 1 2 4 5 3 6 7

//中序遍历
function inOrder(node){
  if(!node) return;
  inOrder(node.left);
  console.log(node.val);
  inOrder(node.right);
 }
//  inOrder(tree); 4 2 5 1 6 3 7

 //后序遍历
function postOrder(node){
  if(!node) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.val);
 }
//  postOrder(tree); 4 5 2 6 7 3 1

 /** 深度优先遍历---栈实现(回溯) */
 //前序遍历
 function preOrderWithStack(root){
   let stack = [root];
   while(stack.length){
      let p = stack.pop();
      console.log(p.val);
      p.right && stack.push(p.right);
      p.left && stack.push(p.left);
   }
 }
//  preOrderWithStack(tree); 

/** 深度优先遍历---栈实现(回溯) */
 //前序遍历
 function preOrderWithStack2(root){
  let stack = [root];
  let res = []
  let node = root;
  while(stack.length){
   while(node !==null){
     res.push(node.val);
     stack.push(node);
     node = node.left;
   }
   if(stack.length){
     node = stack.pop();
     node = node.right;
   }
  }
  return res;
}
//  console.log(preOrderWithStack2(tree)); 1 2 4 5 3 6 7

 /** 广度优先遍历---层序遍历--队列实现 */
 function levelOrder(root){
  let stack = [root];
  while(stack.length){
     let p = stack.shift();
     console.log(p.val);
     p.left && stack.push(p.left);
     p.right && stack.push(p.right);
  }
}
// levelOrder(tree);  1 2 3 4 5 6 7